package org.example.Soution001;

import java.util.ArrayList;
import java.util.List;

public class PathSum3 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1000000000);
        root.left = new TreeNode(1000000000);
        root.left.left = new TreeNode(294967296);
        root.left.left.left = new TreeNode(1000000000);
        root.left.left.left.left = new TreeNode(1000000000);
        root.left.left.left.left.left = new TreeNode(1000000000);
//        root.left.right = new TreeNode(2);
//        root.left.right.right = new TreeNode(1);
//        root.right.right = new TreeNode(11);
        PathSum3 obj=new PathSum3();
        System.out.println(obj.pathSum(root,0));

    }

    int result=0;
    public int pathSum(TreeNode root, int targetSum) {
        if(root!=null){
            pathTree(root,targetSum);
        }
        return result;
    }

    public List<Long> pathTree(TreeNode root, int targetSum){
        List<Long> allPathLength=new ArrayList<>();
        if (root.left != null) {
            allPathLength.addAll(pathTree(root.left,targetSum));
        }
        if (root.right != null) {
            allPathLength.addAll(pathTree(root.right,targetSum));
        }
        allPathLength.add(0L);
        for(int i=0;i<allPathLength.size();i++){
            allPathLength.set(i,allPathLength.get(i)+root.val);
            if(allPathLength.get(i)==targetSum){
                result++;
            }
        }
        return allPathLength;
    }
}
